package vj.matrix;

import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Random;

/*
 * Given an N*N Matrix. All rows are sorted, and all columns are sorted. 
 * Find the Kth Largest element of the matrix.
 * An N*N Matrix. All rows are sorted, and all columns are sorted.
 * Search for a element in the matrix
 */

/*
 * { {2,5,11,17,21}, {4,6,13,19,30 },
				{7,10,14,23,37},{18,25,40,43,49} ,
				{20,36,55,61,76} }
 */
public class SortedMatrix {

	public static int SIZE = 100;
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Random r = new Random();
		
		int mat[][]= { {2,5,11,17,21}, {4,6,13,19,30 },
				{7,10,14,23,37},{18,25,40,43,49} ,
				{20,36,55,61,76} };
		
		printSpiral(mat);
		
		int step = 1000;
		
		int bigMat[][] = new int[SIZE][];
		for(int i = 0; i < SIZE ; i++) {
			int nums[] = new int[SIZE];
			step += 500;
			for(int j = 0; j < nums.length; j ++) {
				nums[j] = r.nextInt(1000) + step;
			}
			Arrays.sort(nums);
			bigMat[i] = nums; 
		}
		printMatix(bigMat);
		
		System.out.println("\n\n\n");
		File op = new File("temp.txt");
		printMatix(bigMat, op);
				
		//System.out.println(find2(bigMat, 4634));
		find(bigMat, 4634);
		printSubMatrix(bigMat, 7, 6, 4, 5);
		
	}

	public static void printMatix(int mat[][]) {
		for(int r = 0; r < mat.length; r++) {
			for(int c = 0; c  < mat[r].length; c++) {
				System.out.print(mat[r][c] + " ");
			}
			System.out.println();
		}
		
	}
	
	public static void printMatix(int mat[][], File op) {
		FileOutputStream fos = null;
		try {
			op.createNewFile();
			fos = new FileOutputStream(op);
			
		} catch (IOException e) {
			e.printStackTrace();
			return;
		}
		PrintStream ps = new PrintStream(fos);
		for(int r = 0; r < mat.length; r++) {
			for(int c = 0; c  < mat[r].length; c++) {
				ps.print(mat[r][c] + " ");
			}
			ps.println();
		}
		
	}
	
	
	
	public static void printSubMatrix(int m[][], int sR, int sC, int r, int c) {
		for(int i = sR; i < sR + r; i++) {
			for(int j = sC; j < sC + c; j++) {
				System.out.print(m[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	/*
	 * Searches for element k in the sub matrix whose start element is at m[sR][sC] and has r rows and c columns 
	 */
	private static boolean find(int m[][], int sR, int sC, int r, int c, int k) {
		for(int i = 0; i < r; i++) {
			// frame the row properly
			int arr[] = m[sR + r];
			if(Arrays.binarySearch(arr, sC, sC + c, k) >= 0)
				return true;
			
		}
		return false;
	}
	
	
	/*
	 * method works for square matrices
	 */
	public static boolean find(int mat[][], int k) {
		int s = mat.length;
		boolean ret = false;
		int d;
		for(d = 0; d < s; d++) {
			if(mat[d][d] == k)
				return true;
			else if(mat[d][d] > k)
				break;
		}
		ret = find(mat, 0, d, s - d, d, k);
		if(!ret)
			ret = find(mat, 0, d, d, s - d, k);
		return ret;
	}
	
	public static boolean find2(int mat[][], int k) {
		for(int r = 0; r < mat.length; r++) {
			int arr[] = mat[r];
			if(Arrays.binarySearch(arr, k) >= 0)
				return true;
		}
		return false;
	}
	
	public static boolean find1(int mat[][], int k) {
		for(int r = 0; r < mat.length; r++) {
			for(int c = 0; c  < mat[r].length; c++) {
				if(mat[r][c] == k)
					return true;
			}
		}
		return false;
	}
	
	/*public int kthLargest(int m[][], int k) {
		for(int r = 0; r < m.length; r++) {
			for(int c = 0; c < m[r].length; c++) {
				
			}
		}
	}*/
	
	public static void printSpiral(int mat[][]) {
		int r = mat.length;
		for(int i = 0; i < r; i++) {
			if((i & 1) == 0) {
				for(int j = 0; j < mat[i].length; j++)
					System.out.print(" " + mat[i][j]);
			} else {
				for(int j = mat[i].length - 1; j >= 0; j--)
					System.out.print(" " + mat[i][j]);
			}
			System.out.println();
		}
		
	}

}
